package org.raymond.iworks.study.basic.algorithm.sort;

/**
 * @author raymond
 * @version V1.0
 * @Description: TODO
 * 冒泡排序的基本思想:
 * 通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,
 * 就像水底下的气泡一样逐渐向上冒.
 * 因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,
 * 因此要在排序过程中设置一个标志判断元素是否进行过交换,从而减少不必要的比较.(优化)
 *
 * init: 79 56 90 4 32 27 16 88 33
 * sort1: 56, 79, 4, 32, 27, 16, 88, 33, 90
 * sort2: 56, 4, 32, 27, 16, 79, 33, 88, 90
 * sort3: 4, 32, 27, 16, 56, 33, 79, 88, 90
 * sort4: 4, 27, 16, 32, 33, 56, 79, 88, 90
 * sort5: 4, 16, 27, 32, 33, 56, 79, 88, 90
 * sort6: 4, 16, 27, 32, 33, 56, 79, 88, 90
 *
 * init: 3,9,-1,10,-2
 * 第一趟排序:
 * 1) 让3与9比较, 3<9, 不变;
 * 2) 让9与-1比较, 9>-1, 相邻的元素逆序就交换;
 * 3) 让9与10比较, 9<10, 不变;
 * 4) 让10与-2比较, 10>-2, 交换;
 * 得到: 3,-1,9,-2,10
 *
 * 1. (3, 9), -1, 10, -2
 * 2. 3, (-1, 9), 10, -2
 * 3. 3, -1, (9, 10), -2
 * 4. 3, -1, 9, (-2, 10)
 * 第二躺排序:
 * 1. (-1, 3), 9, -2, 10
 * 2. -1, (3, 9), -2, 10
 * 3. -1, 3, (-2, 9), 10
 * 4. -1, 3, -2, 9, 10
 * 第三趟排序:
 * 1. (-1, 3), -2, 9, 10
 * 2. -1, (-2, 3), 9, 10
 * 3. -1, -2, (3, 9), 10
 * 4. -1, -2, 3, 9, 10
 * 第四趟排序:
 * 1. (-2, -1), 3, 9, 10
 * 2. -2, (-1, 3), 9, 10
 * 3. -2, -1, 3, 9, 10
 * 第五趟排序:
 * 1. -2, -1, 3, 9, 10
 *
 * 总结规则:
 * 1. 一共进行数组的大小-1次大的循环
 * 2. 每轮排序次数在逐渐减少
 */
public class BubbleSortingTest {
    public static void main(String[] args) {
        int[] arr = new int[100000];
        for(int i=0; i<arr.length; i++){
            arr[i]=(int)(Math.random()*100000000);
        }
        //arr = new int[]{79,56,90,4,32,27,16,88,33};
        //arr = new int[]{3,9,-1,10,-2};
        //System.out.printf("待排序数组:%s\n", Arrays.toString(arr));
        long start = System.nanoTime();
        test2(arr);
        long end = System.nanoTime();
        //System.out.printf("排序结果:%s\n", Arrays.toString(arr));
        // post: 25733647600 纳秒,约26秒, 100000个元素的数组
        System.out.printf("耗时:%d\n", (end-start));

        start = System.nanoTime();
        SelectSortTest.jdkSort(arr);
        end = System.nanoTime();
        // post: 3808700 纳秒, 约3.8毫秒, 100000个元素的数组
        System.out.printf("jdksort 耗时:%d\n", (end-start));
    }

    public static void test1(){
        int arr[] = {3,9,-1,10,10};
        for(int i=0; i<arr.length; i++) {
            // 没轮排序都能确定至少一个倒数第i个位置的正确数据,因此下一轮可以减少最后i次比较
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
            //System.out.printf("第%d轮排序后的数组:\n", i+1);
            //System.out.printf("%s\n", Arrays.toString(arr));
        }
    }

    // 优化
    public static void test2(int[] arr){
        boolean flag = false;
        for(int i=0; i<arr.length; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                // 比较的是相邻两个数,因此放在第二层for循环内比较
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
            //System.out.printf("第%d轮排序后的数组:\n", i+1);
            //System.out.printf("%s\n", Arrays.toString(arr));
            // 一次交换都没有发生
            if(!flag){
                break;
            }else{
                // 每轮排序后需要重置,为下一轮排序初始化标记
                flag = false;
            }
        }

    }
}
